package scala.examples.fs;

/*
 TODO: - type parameters
       - (partial) type application
       - pattern matching
       - lambda's
       - multi-methods
       - structural types
       - metaprogramming
*/
object Syntax {
  def debug[t,a](s :t):a =  null //Debug.syntax.log(s)
  
  def showTree[T](e :T) :String = {
    var i = 0
    def twoParens(c :Char) :Boolean = {if(c equals '(') i=i+1; if(i>1) false else true}
    e.toString.toList.takeWhile(twoParens).mkString("","","")
  }
  
  type Loc = int;  // TODO: parameterise Loc by the type of the value it references? (dependent types...) 

  trait Term {
        // @result == true || @result == false
  	def isPath = false
  }
  
  trait BuiltinTerm extends Term // used as body of builtin members (during evaluation)
    case object BuiltinPrintln extends BuiltinTerm
    case object BuiltinPrint extends BuiltinTerm
    case object BuiltinError extends BuiltinTerm
    
  case class TypedTerm(term: Term, typ: Type) extends Term {
    override def isPath = term.isPath
  }
  
  trait Value extends Term;
          case object Null extends Value;
          case object True extends Value;
          case object False extends Value;  
          case class StringLit(s :String) extends Value;  
          //case class IntLit(i :Int) extends Value;  
          case class Closure(args :List[Arg], t: Type, body: Term) extends Value; // TODO: escaping vars, ..

  // trait Path {}            
  case class Name(name: String) extends Term /*with Path*/ {
    override def isPath = true
  }
          
  case class Ref(x: Loc, name: String) extends Value /*with Path*/  {
    override def isPath = true
  }
  
  case class Select(e: Term, label: String) extends Term /*with Path if(e.isInstanceOf[Path])*/ {
    override def isPath = e.isPath 
  }


  case class If(cond: Term, then: Term, els: Option[Term]) extends Term;
  case class Apply(fun: Term, args: List[Term]) extends Term;
  case class New(p: Term) extends Term;
  case class LocalVal(name: String, tpe: Option[Type], value :Term, scope: Term) extends Term;
  case class ClassDef(name: String, c: ClassSig, e: Term) extends Term;

  trait Type;
          case class Inst(e: Term) extends Type
          case class Single(e: Term) extends Type
          case class Class(c: ClassSig) extends Type
          case class TypeSelect(t: Type, label: String) extends Type
          case class FunType(ts: List[Type]) extends Type
          case class BuiltinTypeFs extends Type // the type of the builtin variable $fs$

  trait StoreItem;
          case class ClassSig(ps: List[Term], self: String, selfT: Type, ms: List[Member]) 
               extends StoreItem {
            // not too happy about this, but necessary, as giving 'this' a structural type doesn't work (no longer related to the corresponding nominal type)
            // (but that's the only option if you don't include an explicit type)
            val selfType = if(selfT==null) Class(this) else selfT
          }
          case class Obj(c: Term, ms: List[Member]) extends StoreItem;

  // TODO: make hierarchy more elegant, but need some way to easily match on Val[def/dcl] --> need common superclass 
  // good case for views for pattern matching
  trait Member {
    def label: String
    def signature: Member
    def corresponds(other: Member): Boolean = this.label equals other.label // TODO: make more precise (i.e., simple cases, in case of overloading, ...)
  }
  
  trait Declaration extends Member {
    def signature = this
  }
  
  trait Definition extends Member;

  case class ValSig(l: String, t: Type, value: Option[Term]) extends Member { 
    def label = l
    def signature: Member = new ValSig(l,t,None)
  }
  
  class ValDcl(l: String, t: Type) extends ValSig(l, t, None) with Declaration {
    override def signature = this
  }
  class ValDef(l: String, t: Type, e: Term) extends ValSig(l, t, Some(e)) with Definition {
    override def signature: Member = new ValDcl(l,t)
  }

  case class DefSig(l: String, args :List[Arg], t: Type, body: Option[Term]) extends Member { 
    def label = l
    def signature: Member = new DefSig(l, args, t, None)
  }
  
  class DefDcl(l: String, args :List[Arg], t: Type)  extends DefSig(l, args, t, None) with Declaration {
    override def signature = this
  }
  
  class DefDef(l: String, args :List[Arg], t: Type, body: Term) extends DefSig(l, args, t, Some(body)) with  Definition {
    override def signature: Member = new DefDcl(l, args, t)
  }

  case class Arg(name: String, typ: Type)
  
  
  case class TypeDcl(l: String, upperbound: Option[Type]) extends Member with Declaration {
    upperbound match { case Some(_) => error("Type declarations with upper-bound not handled yet") case _ =>} // TODO
    def label = l
    override def signature = this
  }
  
  case class TypeDef(l: String, t: Type) extends Member with Definition {
    def label = l
    override def signature = this
  }

  def ValSigCtor(m: ValSig) = (m match { case ValSig(l,t,o) => &ValSig_ case o: ValDcl => &ValDcl_ case o: ValDef => &ValDef_})
  def ValDcl_(l: String,  t: Type, o: Option[Term]) = o match { case None => new ValDcl(l, t)}
  def ValDef_(l: String,  t: Type, o: Option[Term]) = o match { case Some(e) => new ValDef(l, t, e)}
  def ValSig_(l: String,  t: Type, o: Option[Term]) = ValSig(l, t, o)
  def ValDcl(l: String,  t: Type) = new ValDcl(l, t)
  def ValDef(l: String,  t: Type, e: Term) = new ValDef(l, t, e)

  def DefSigCtor(m: DefSig) = (m match { case DefSig(l,a,t,o) => &DefSig_ case o: DefDcl => &DefDcl_ case o: DefDef => &DefDef_})
  def DefDcl_(l: String,  args :List[Arg], t: Type, o: Option[Term]) = o match { case None => new DefDcl(l, args, t)}
  def DefDef_(l: String,  args :List[Arg], t: Type, o: Option[Term]) = o match { case Some(e) => new DefDef(l, args, t, e)}
  def DefSig_(l: String,  args :List[Arg], t: Type, o: Option[Term]) = DefSig(l, args, t, o)
  def DefDcl(l: String, args :List[Arg], t: Type)  = new  DefDcl(l, args, t)
  def DefDef(l: String, args :List[Arg], t: Type, body: Term) = new DefDef(l, args, t, body)


  
  // maps from locations --------------------------------------------------

    class LocMap[T <: AnyRef] {
      val nextLoc: Loc = 0;
      def apply(n: Loc): T = null;
      def update(n: Loc, newitem: T): LocMap[T] = null;

      // result(old.nextLoc) == item
      def extend(item: T): LocMap[T] = new LocMap[T] {
        override val nextLoc: Loc = 
          LocMap.this.nextLoc + 1;
        override def apply(n: Loc): T = 
          if (n == nextLoc-1) item else LocMap.this.apply(n);
        override def update(n: Loc, newitem: T): LocMap[T] = 
          if (n == nextLoc-1) LocMap.this.extend(newitem)
          else LocMap.this.update(n, newitem).extend(item)
      }
    }
  // maps & substitution ----------------------------------------------

    	// perfect candidate for DGP! -- this class would be unnecessary
  class Map {
    def term(e: Term): Term = e match {
      case Select(e1, l) => Select(term(e1), l)
      case New(p) => New(term(p))
      case LocalVal(name, optType, value, scope) => LocalVal(name, option(typ,optType), term(value), term(scope))
      case ClassDef(n, c, e) =>	ClassDef(n, classSig(c), term(e))
      case If(cond, then, optElse) => If(term(cond), term(then), option(term,optElse))
      case Apply(fun, args)  =>  Apply(term(fun), args map term)    
      case TypedTerm(e, t)  =>  TypedTerm(term(e), typ(t))    
      case _ => e
    }
    def classSig(c: ClassSig): ClassSig = c match {
      case c @ ClassSig(ps, self, st, ms) =>
	ClassSig(ps map term, self, (if(st!=null)  typ(st) else null), ms map member)
    }
    def typ(t: Type): Type = t match {
      case Inst(e)          => Inst(term(e))
      case Single(e)        => Single(term(e))
      case Class(c)         => Class(classSig(c))
      case TypeSelect(t, l) => TypeSelect(typ(t), l)
      case FunType(ts) => FunType(ts map typ)
    }
    
    def option[t,s](fun: t=>s, o: Option[t]) :Option[s] = o match {
      case Some(obj) => Some(fun(obj))
      case None => None
    }
    
    def members(ms: List[Member]): List[Member] = {
      for(val m <-ms) yield member(m)
    }
    
    def member(m: Member): Member= m match { // TODO: why doesn't GADT mechanism work?
      case ValSig(l, t, o)    => ValSigCtor(m.asInstanceOf[ValSig])(l, typ(t), option(term, o))
      case DefSig(l, args, t, o) => DefSigCtor(m.asInstanceOf[DefSig])(l, args map {case Arg(n,at) => Arg(n,typ(at))}, typ(t),option(term, o))
      case TypeDcl(l, t)   => TypeDcl(l, option(typ,t))
      case TypeDef(l, t)   => TypeDef(l, typ(t))
    }
  }

  	/* e.map( Name(name) => to |||  
                  New(name, p, e) => e  |||
                  ClassDef(name, c, e) => e |||
                  ClassSig(ps, name, ms) => ClassSig(ps map term, name, ms))
            // order of traversal is important!
	            // once a ClassSig has been visited, don't traverse its members
	            // 
  	*/	

  class Once[a] {
     var done = false
     var res: a = _
     def once(fun: =>a): a = {if(!done){res=fun; done=true}; res}
  }
          
  def subst(name: String, to: Term) :Map = new Map {
    val shownScope = new Once[unit]
    debug("<subst name=\""+name+"\" to=\""+to+"\">")
    

    
    override def member(m: Member): Member = {
      var showNew=false
      shownScope.once{debug("<orig>"+(show member m)+"\n</orig>"); showNew=true}
      
      val r = super.member(m)

      if(showNew)
        debug("<new>"+(show member r)+"\n</new>\n</subst>\n")
      r
    }
    
    override def term(e: Term): Term = {     
      var showNew=false
      shownScope.once{debug("<orig>"+(show term e)+"\n</orig>"); showNew=true}

      val r = e match {
       case Name(n) if (name == n) => to
       
       // avoid capture: if we're renaming some free variable in our scope *to* our bound variable, first change our bound name 
       case LocalVal(n, t, v, scope) if (name != n && (to match { case Name(n2) => n == n2 case _ => false})) => 
         val newN = n+"_"
         val newScope = subst(n, Name(newN)) term scope
         term(LocalVal(newN, t, v, newScope))

       // name is bound in scope, only substitute other terms/types
       case LocalVal(n, t, v, scope) if (name == n) => 
         LocalVal(n, option(typ,t), term(v), scope)
       
       // avoid capture: if we're renaming some free variable in our scope *to* our bound variable, first change our bound name 
       case ClassDef(n, scope1, scope2 ) if (name != n && (to match { case Name(n2) => n == n2 case _ => false})) => 
         val newN = n+"_"
         val subs = subst(n, Name(newN))
         val newScope1 = subs classSig scope1
         val newScope2 = subs term scope2
         term(ClassDef(newN, newScope1, newScope2))
         
       case ClassDef(n, scope1, scope2 ) if (name == n) => e
       
       case _ => super.term(e)
      }
      
      if(showNew)
        debug("<new>"+(show term r)+"\n</new>\n</subst>\n")
        
      r
    }
    
    override def classSig(c: ClassSig): ClassSig = {
      var showNew=false
      shownScope.once{debug("<orig>"+(show classSig c)+"\n</orig>"); showNew=true}
      
      val r = c match {
        // avoid capture
        case ClassSig(ps, n, st, scope) if (name != n && (to match { case Name(n2) => n == n2 case _ => false})) => 
          val newN = n+"_"
          val newScope = subst(n, Name(newN)) members scope
          classSig(ClassSig(ps, newN, st, newScope))
        
        case ClassSig(ps, n, st, scope) if name == n =>  // self name is bound in members
           ClassSig(ps map term, n, st, scope)
           
        case _ => super.classSig(c)
      }

      if(showNew)
        debug("<new>"+(show classSig r)+"\n</new>\n</subst>\n")
        
      r
    }
  }
	       


  // pretty printing -------------------------------------------------------
	 // generic fold with + as combinator 
	 // (could you also interpret this in the string concatenation idiom ??)
  class Show(indent: String) {
    private val delta = "  ";

    def newLine: String = "\n" + indent;

    def term(e: Term): String = e match {
      case Null => "null"
      case Name(x) => x
      case True => "true"
      case False => "false"
      case StringLit(s) => "\"" + s + "\""
      case If(cond, then, Some(els)) => "if(" + term(cond) + ") " + atomicTerm(then) + " else " + atomicTerm(els)
      case If(cond, then, None) =>  "if(" + term(cond) + ") " + term(then)
      case Apply(fun, args) => term(fun) + args.map(term).mkString("(", ", ", ")")
      case Select(e1, l) => atomicTerm(e1) + "." + l;
      case Ref(x, n) => "*("+n+")"
      case LocalVal(name, Some(tpe), value, scope) => "(val " + name + ": " + typ(tpe) + " = " + term(value) + "); "+term(scope) 
      case LocalVal(name, None, value, scope) => "(val " + name + " = " + term(value) + "); "+term(scope)
      case New(p) => 
	"new " + term(p) 
      case ClassDef(x, c, e) => 
	"class " + x + " extends " + classSig(c) + ";" + newLine + term(e)
      case TypedTerm(e, t)  => atomicTerm(e) + ": "+ typ(t)     
      case x => if(x==null) "null" else x.toString
    }
        
    def atomicTerm(e: Term): String = e match {
      case LocalVal(_, _, _, _) | ClassDef(_, _, _) => "(" + term(e) + ")"
      case _ => term(e)
    }
    def classSig(c: ClassSig): String = c match {
      case ClassSig(ps, self, st, ms) =>
	val show1 = new Show(indent + delta);
	ps.map(term).mkString("", ", ", "{ ") + self + (if(st!=null) ": " + typ(st) else "") +
	ms.map(show1.member).mkString(" | ", "", newLine) + "}"
    }
    def typ(t: Type): String = t match {
      case Inst(e)          => term(e) + ".inst"
      case Single(e)        => term(e) + ".type"
      case Class(c)         => "class " + classSig(c)
      case TypeSelect(t, l) => typ(t) + "#" + l;
      case FunType(ts) => (ts map typ).mkString("","=>","")
      case BuiltinTypeFs() => "$FS$"
    }
    
    def args(a: List[Arg]) :String = a.map(x => x match{case Arg(n, tpe) => n+": "+typ(tpe)}).mkString("(", ", ", ")")

    def option[t](fun: t=>String, o: Option[t]) :String = o match {
      case Some(obj) => fun(obj)
      case None => ""
    }
  
    def members(ms: List[Member]): String = {
      (for(val m <-ms) yield member(m)).mkString("","\n","")
    }
    
    def member(m: Member): String = newLine + (m match {
      case ValSig(l, t, b) => 
	"val " + l + ": " + typ(t) + option(((x :Term) => " = "), b) + option(atomicTerm, b)
      case DefSig(l, a, t, b) => 
        "def " + l + args(a) + ": " + typ(t) + option(((x :Term) => " = "), b) + option(atomicTerm, b)
      case TypeDcl(l, t) => 
	"type " + l + option(((x :Type) => " <: "),t) + option(typ,t)
      case TypeDef(l, t) => 
	"type " + l + " = " + typ(t)
    });
  }
  val show = new Show("");
}
